package ling.learn.graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Graph {
  private Map<String, List<Edge>> adjList;

  public Graph() {
    this.adjList = new HashMap<>();
  }

  public void addEdge(String from, String to, String content) {
    adjList.computeIfAbsent(from, k -> new ArrayList<>()).add(new Edge(to, content));
  }

  public List<List<String>> findAllPaths(String start, String end) {
    List<List<String>> paths = new ArrayList<>();
    List<String> path = new ArrayList<>();
    Set<String> visited = new HashSet<>();
    dfs(start, end, visited, path, paths);
    return paths;
  }

  private void dfs(String current, String end, Set<String> visited, List<String> path,
      List<List<String>> paths) {
    visited.add(current);
    path.add(current);
    if (current.equals(end)) {
      paths.add(new ArrayList<>(path));
    } else {
      List<Edge> neighbors = this.adjList.getOrDefault(current, new ArrayList<>());
      for (Edge edge : neighbors) {
        if (!visited.contains(edge.to)) {
          dfs(edge.to, end, visited, path, paths);
        }
      }
    }
    path.remove(path.size() - 1);
    visited.remove(current);
  }

  public String formatPath(List<String> path) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < path.size(); i++) {
      sb.append(path.get(i));
      if (i < path.size() - 1) {
        Edge edge = getEdge(path.get(i), path.get(i + 1));
        if (edge != null) {
          sb.append("(").append(edge.content).append(")");
        }
        sb.append("->");
      }
    }
    return sb.toString();
  }

  private Edge getEdge(String from, String to) {
    List<Edge> edges = this.adjList.get(from);
    if (edges != null) {
      for (Edge edge : edges) {
        if (edge.to.equals(to)) {
          return edge;
        }
      }
    }
    return null;
  }
}
